/*
    7-5 自守数
数学的世界有很多很漂亮的数字或者数字集合，比如梅森数，哥德巴赫猜想，水仙花数，完全数，自守数。
今天我们就一起来探究一下自守数。自守数是指一个数的平方的尾数等于该数自身的自然数。
例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。
请求出n以内的自守数的个数

输入格式:
第一行输入n,随后输入n个数m。

输出格式:
在一行中输出m以内自守数的个数，所有输出在一行内完成，末尾没有多余空格。
*/
//这里是第一版的代码，该方法会超时
//判断自守数的函数用的是pow，用pow求出指定数字的后几位来判断
#include<bits/stdc++.h>
using namespace std;
bool fun(int i){
	int a=i;
	long long temp=i*i;
	string s=to_string(i);
    int len=s.size();
    int m=pow(10,len);
	

	
	if(a==(temp%m)) return true;
	else return false;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		int m;cin>>m;
        int sum=0;
		for(int i=0;i<=m;i++){
			if(fun(i)) sum++;
		}
		cout<<sum;
        if(n) cout<<" ";
	}
}